CodeWars 題目

Link

難度

5 kyu

題目

尋找最大子陣列的和，包含空陣列。

思路

從 index 0 為起點，每次都計算 start - end 的總和，比對是否較大。
end 如果到最後一位，start 遞增，end = start。

直到 start 到最後一位為止。

pseudo code

let start = 0
let end = 0
let max = -Infinity
let total

while loop start < arr.length - 1 如果 subarray 的起始到達陣列最尾，跳出循環
total = 0 每次循環都把總和重加
for loop start...end total += arr[?]
if(total > max) max = total

判斷 subarray 的頭尾
if end == arr.length - 1
start++
end = start
else
end++

實作

var maxSequence = function (arr) {
   if (arr.length === 0) return 0;
   let allNegative = arr.filter(item => item > 0);
   if (allNegative.length === 0) return 0;
  
   let start = 0;
   let end = 0;
   let maxValue = -Infinity;
   let sum;
  
   while (start < arr.length - 1) {
      sum = 0;
      for (let i = start; i <= end; i++) {
         sum += arr[i];
      }
      if (sum > maxValue) maxValue = sum;
      if (end >= arr.length - 1) {
         start++;
         end = start;
      } else {
         end++;
      }
   }
   return maxValue;
}

如果陣列長度為 0，直接返回 0。

filter 過濾元素為負數的，如果最後全負數也是返回 0。

宣告子陣列的 start 以及 end，while 迴圈在 start 跑到陣列最後位時會停止。

在每一次的迴圈都會把 sum 重新賦值為 0。

for loop 累加 start 到 end 的子陣列，取得總和與 maxValue 比對。

如果 sum > maxValue，則把 maxValue = sum。

判斷目前所在的 end 位置，如果到了陣列最後位，則 start 往前、end 提到 start 的下一個；否則繼續累加 end，直到最後返回 maxValue。

他人的解法

var maxSequence = function(arr){
  var min = 0, ans = 0, i, sum = 0;
  for (i = 0; i < arr.length; ++i) {
    sum += arr[i];
    min = Math.min(sum, min);
    ans = Math.max(ans, sum - min);
  }
  return ans;
}

i 宣告在 for loop 之外；

紀錄最小值 min = 0, 紀錄解答（最大值） ans = 0, 紀錄每次的總和 sum = 0。

在每次的循環，sum 會累加 arr[i]；
min 是追蹤當前位置之前的最小和；ans 紀錄最大的子陣列。
以陣列帶入 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 為例：

1. i = 0，sum = -2，min = -2，ans = 0。
2. i = 1，sum = -1，min = -2，ans = 1。
3. i = 2，sum = -4，min = -4，ans = 3。
4. i = 3，sum = 0，min = -4，ans = 7。
5. i = 4，sum = -1，min = -4，ans = 7。
6. i = 5，sum = 1，min = -4，ans = 7。
7. i = 6，sum = 2，min = -4，ans = 7。
8. i = 7，sum = -3，min = -4，ans = 7。
9. i = 8，sum = 1，min = -4，ans = 7。

-4 的 min 組成是子陣列 [-2, 1, -3]。
sum 表示的就是累加到當前的子陣列，min 本身也是從 0 累加的子陣列。
sum - min 是為了確保目前的 ans 所記錄的是最大的子陣列。

假設 index 0 - 3 為 min，sum 已經計算到 index 0 - 6；
sum - min 之後，就是在比對 index 4 - 6 是否存在比 ans 更大的可能。

心得

這題的最佳解燒了我的腦袋，看了討論區貌似是數學相關的巧思。